/**
 * 需求: 打印回形矩阵 <br>
 * 根据输入的边长, 打印一个回形矩阵
 * <p>
 * 比如如输入 3,输出   <br>
 * [                 <br>
 * [1, 2, 3],        <br>
 * [8, 9, 4],        <br>
 * [7, 6, 5]         <br>
 * ]
 * <hr>
 * 算法: 类似于环状替换和旋转图像, 将矩阵分为圈, 每一圈都是自增的, 将一圈分为上下左右四个 step , 每个 step 是每一圈的边长-1
 * <br>
 * 时间复杂度: O(n^2), n 为矩阵边长
 * <br>
 * 空间复杂度: O(1)
 * <p>
 * 知识点: 回形矩阵
 * <br>
 *
 * @author yonxao
 * @since  2022/5/27
 */
class BackShapedMatrix {
    public static void main(String[] args) {
        // Scanner in = new Scanner(System.in);
        // System.out.println("输入一个非负整数: ");
        // int length = in.nextInt();
        int length = 4;
        int[][] backShapedMatrix = backShapedMatrix(length);
        printBackShapedMatrix(backShapedMatrix);
    }


    /**
     * 类似于环状替换和旋转图像, 将矩阵分为圈, 每一圈都是自增的, 将一圈分为上下左右四个 step , 每个 step 是每一圈的边长-1
     * <br>
     * 时间复杂度: O(n^2), n 为矩阵边长
     * <br>
     * 空间复杂度: O(1)
     * <p>
     * 知识点: 回形矩阵
     */
    public static int[][] backShapedMatrix(int length) {
        int[][] matrix = new int[length][length];
        int lengthSubOne = length - 1;
        // 圈数
        int loop = length / 2;

        // 边长为奇数时, 处理中心点
        if (length % 2 == 1) {
            matrix[loop][loop] = length * length;
        }

        // 填充的数是从 1 - length * length, 一圈是填充 4 * step, 一个 step 填充 4 个数
        int start = 1;
        for (int i = 0; i < loop; i++) {
            int step = lengthSubOne - i * 2;
            // step = 1, i = 1; j < 1, start = 13
            for (int j = 0; j < step; j++) {
                // 左
                matrix[i][i + j] = start + j;
                // 下
                matrix[j + i][lengthSubOne - i] = start + step + j;
                // 右
                matrix[lengthSubOne - i][lengthSubOne - j - i] = start + step * 2 + j;
                // 上
                matrix[lengthSubOne - j - i][i] = start + step * 3 + j;
            }
            start += step * 4;
        }
        return matrix;
    }


    private static void printBackShapedMatrix(int[][] backShapedMatrix) {
        for (int[] row : backShapedMatrix) {
            for (int e : row) {
                System.out.print(e + "\t");
            }
            System.out.println();
        }
        System.out.println();
    }
}
